这道题应该算是 的前置知识了吧。可惜之前我并没有做过。
对于一棵以 为根的子树，它的重心只可能在点 或 以点 的重儿子为根的子树中。
那么类比 倍增父亲，树的重心倍增重儿子。
查询时保证倍增时的子树大小不小于原子树大小的一半（重心的定义）。
最后它和它的父节点都可能是重心，随便判一下就可以了。
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 300000 , MAXK = 20;
int n , q;
vector< int > Graph[ MAXN + 5 ];
int Fa[ MAXN + 5 ] , Size[ MAXN + 5 ] , Hson[ MAXN + 5 ] , Anc[ MAXN + 5 ][ MAXK + 1 ];
void dfs( int u ) {
Size[ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
int v = Graph[ u ][ i ];
dfs( v ); Size[ u ] += Size[ v ];
if( Size[ v ] > Size[ Hson[ u ] ] ) Hson[ u ] = v;
}
Anc[ u ][ 0 ] = Hson[ u ];
for( int i = 1 ; i <= MAXK ; i ++ ) Anc[ u ][ i ] = Anc[ Anc[ u ][ i - 1 ] ][ i - 1 ];
}
bool chk( int u , int v ) { //以u为根的子树，v是否为重心
return max( Size[ Hson[ v ] ] , Size[ u ] - Size[ v ] ) <= Size[ u ] / 2;
}
int Query( int rt ) {
int u = rt;
for( int i = MAXK ; i >= 0 ; i -- )
if( Anc[ u ][ i ] && Size[ Anc[ u ][ i ] ] >= Size[ rt ] / 2 ) u = Anc[ u ][ i ];
if( chk( rt , u ) ) return u;
if( chk( rt , Fa[ u ] ) ) return Fa[ u ];
}
int main( ) {
scanf("%d %d",&n,&q);
for( int i = 2 ; i <= n ; i ++ ) {
scanf("%d",&Fa[ i ]);
Graph[ Fa[ i ] ].push_back( i );
}
dfs( 1 );
for( int i = 1 , rt ; i <= q ; i ++ ) {
scanf("%d",&rt);
printf("%d\n", Query( rt ) );
}
return 0;
}